P5176 公约数 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 15分钟 | 2336字数 首先有一个结论: gcd(i⋅j,i⋅k,j⋅k)=gcd(i,j)⋅gcd(j,k)⋅gcd(i,k)gcd(i,j,k)gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)} gcd(i⋅j,i⋅k,j⋅k)=gcd(i,j,k)gcd(i,j)⋅gcd(j,k)⋅gcd(i,k) 阅读全文 »
SP1026 FAVDICE - Favorite Dice 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 2分钟 | 302字数 令 dp[i]dp[i]dp[i] 表示当前已经得到了 iii 个面后的期望次数。 有两种情况: 1.掷出已有的面,概率为 in\frac{i}{n}ni 阅读全文 »
P4900 食堂 发布于 2020-09-12 | 分类于 数学 、 数论 | 4分钟 | 576字数 题目需要求的是这个式子: ∑i=AB∑j=1i{ij}\sum_{i=A}^B\sum_{j=1}^i \{\frac{i}{j}\} i=A∑Bj=1∑i{ji} 阅读全文 »
P3327 [SDOI2015]约数个数和 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 744字数 首先有一个公式: d(ij)=∑x∣i∑y∣j[(i,j)=1]d(ij)=\sum_{x|i}\sum_{y|j}[(i,j)=1] d(ij)=x∣i∑y∣j∑[(i,j)=1] 阅读全文 »
CF464D World of Darkraft - 2 发布于 2020-09-12 | 分类于 概率dp | 3分钟 | 497字数 首先明确一点,所有装备的期望相同,只需求出任意一种后答案乘 kkk 即可。 令 dp[i][j]dp[i][j]dp[i][j] 表示还需要打 iii 只怪,装备等级为 jjj 的金币数量期望。 那么有三种情况: 阅读全文 »
CF398B Painting The Wall 发布于 2020-09-12 | 分类于 概率dp | 5分钟 | 833字数 先考虑所有格子均未涂色的情况。 因为格子的涂色只会影响一行一列,所以可以设 dp(i,j)dp(i,j)dp(i,j) 表示还需要涂 iii 行 , jjj 列的期望步数。 1.涂色格所在行列均未染色,由 dp(i−1,j−1)dp(i-1,j-1)dp(i−1,j−1) 转移,概率为 in×jn\frac{i}{n} \times \frac{j}{n}ni×nj 阅读全文 »
P3501 [POI2010]ANT-Antisymmetry 发布于 2020-09-12 | 分类于 回文自动机 | 2分钟 | 296字数 看到求回文串就想到 PAM\text{PAM}PAM 。 因为只有 0,10,10,1 所以判断条件改成等于。 不过这道题满足题意的串长度一定为偶,所以不能走到 −1-1−1 根。 阅读全文 »
P1891 疯狂LCM 发布于 2020-09-12 | 分类于 数论 | 4分钟 | 516字数 ∑i=1nlcm(i,n)\sum_{i=1}^n lcm(i,n) i=1∑nlcm(i,n) ∑i=1ni∗ngcd(i,n)\sum_{i=1}^n \frac{i*n}{gcd(i,n)} 阅读全文 »
P3911 最小公倍数之和 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 817字数 简单问题复杂化是解决问题的一个好方法。 令 cic_ici 表示 iii 出现的次数,nnn 为最大数字。 ∑i=1n∑j=1nci×cj×lcm(i,j)\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j) 阅读全文 »
P6156 简单题 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 6分钟 | 983字数 ∑i=1n∑j=1n(i+j)kf(gcd(i,j))gcd(i,j)\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j) i=1∑nj=1∑n(i+j)kf(gcd(i,j))gcd(i,j) 显然 f(i)=μ2(i)f(i)=\mu^2(i)f(i)=μ2(i) 阅读全文 »